package cn.xiaolang.function.data_structure;

import lombok.Data;

/**
 * 链表求和:
 * 给定两个用链表表示的整数，每个节点包含一个数位。
 * 这些数位是反向存放的，也就是个位排在链表首部。
 * 编写函数对这两个整数求和，并用链表形式返回结果。
 * <p>
 * 示例：
 * 输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
 * 输出：2 -> 1 -> 9，即912
 * 进阶：假设这些数位是正向存放的，请再做一遍。
 * <p>
 * 示例：
 * 输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
 * 输出：9 -> 1 -> 2，即912
 *
 * @author fuhw/Dean
 * @date 2020-06-12
 */
public class No15SumLinkNode {

    public static void main(String[] args) {

        ListNode one = new ListNode(7);
        ListNode n1 = new ListNode(1);
        ListNode n6 = new ListNode(6);
        one.next = n1;
        n1.next = n6;


        ListNode two = new ListNode(5);
        ListNode n9 = new ListNode(9);
        ListNode n2 = new ListNode(2);
        two.next = n9;
        n9.next = n2;

        System.out.println(addTwoNumbers(one, two));

    }

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户
     * 内存消耗：41 MB, 在所有 Java 提交中击败了97.33%的用户
     * <p>
     * 示例： (7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295= 912
     * 思路：
     * 1. 一位一位的计算，大于10则进位
     * 2. 通过游标控制节点移动，只要有一个不为空，就接着计算
     * 3. 每一位的计算结果存储在result中，resultNext来控制结果的位置
     * 4. 边界处理，最后一位如果进位
     *
     * 时间复杂度：O(max(m,n))，其中 mm 和 nn 分别为两个链表的长度
     */
    public static ListNode addTwoNumbers(ListNode one, ListNode two) {
        ListNode oneCursor = one;
        ListNode twoCursor = two;
        boolean isCarry = false;
        ListNode result = null;
        ListNode resultCursor = null;

        // 2. 只要有一个不为空，就接着计算
        while (oneCursor != null || twoCursor != null) {
            // 1.一位一位的计算，大于10则进位
            // 7 + 5 = 12
            // 1 + 9 = 10
            int plusRes = (oneCursor == null ? 0 : oneCursor.val) + (twoCursor == null ? 0 : twoCursor.val);
            if (isCarry) {
                plusRes++;
                isCarry = false;
            }
            // 2
            if (plusRes >= 10) {
                isCarry = true;
                plusRes = plusRes - 10;
            }
            // 移动节点位数
            oneCursor = oneCursor == null ? null : oneCursor.next;
            twoCursor = twoCursor == null ? null : twoCursor.next;

            // 3. 每一位的计算结果存储在result中，resultNext来控制结果的位置。
            if (result == null) {
                // 计算没结束，空置一个新节点做resultCursor
                result = new ListNode(plusRes, (oneCursor != null || twoCursor != null || isCarry) ? new ListNode() : null);
                resultCursor = result.next;
            } else {
                resultCursor.val = plusRes;
                // 计算没结束，空置一个新节点做resultCursor
                resultCursor.next = (oneCursor != null || twoCursor != null || isCarry) ? new ListNode() : null;
                resultCursor = resultCursor.next;
            }
            // 置空计算下一位
            plusRes = 0;
        }
        //  4. 边界处理，最后一位如果进位
        if (isCarry) {
            resultCursor.val = 1;
        }
        return result;
    }

    @Data
    static class ListNode {
        Integer val;
        ListNode next;

        public ListNode() {
        }

        ListNode(Integer x) {
            val = x;
        }

        public ListNode(Integer val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}




